#include <iostream>
#include <unordered_map>
#include <list>
#include <map>


using std::unordered_map;
using std::map;
using std::list;
using std::cout;
using std::endl;
using std::pair;
using std::make_pair;

class LRUCache
{
public:
    LRUCache(int capacity);
    int get(int key);
    void put(int key, int value);

private:
    unordered_map<int, pair<int, list<int>::iterator>> _cache;
    list<int> _order;
    int _size;
    int _capacity;
};

LRUCache::LRUCache(int capacity)
    : _size(0)
    , _capacity(capacity){}

int LRUCache::get(int key){
    auto it = _cache.find(key);
    if(it == _cache.end()){
        return -1;
    }else{
        _order.splice(_order.begin(), _order, it->second.second);
        return it->second.first;
    }
    return -1;
}

void LRUCache::put(int key, int value)
{
    auto it = _cache.find(key);
    if(it != _cache.end()){
        it->second.first = value;
        _order.splice(_order.begin(), _order, it->second.second);
        return;
    }
    // TODO:
    // it == _cache.end()
    _order.push_front(key);
    _cache.insert(make_pair(key, make_pair(value, _order.begin())));
    if(_size != _capacity){
        ++_size;
    }
    else if(_size == _capacity){
        _cache.erase(*(--_order.end()));
        _order.erase(--_order.end());
    }
    return;
}